package 字符串;

/**
 * 42：接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 思路：此题需要采用贪心的思想，
 * 最基础的思路：如果右边的柱子比左边的柱子高，则当前柱子可以接雨水，统计出当前柱子区域的雨水量，继续遍历，直到遍历完所有柱子
 *
 假设我有一个数组，比如[0,1,0,2,1,0,1,3,2,1,2,1]，这表示有12个柱子，高度分别是0,1,0,2,1,0,1,3,2,1,2,1。下雨后，雨水会积在凹陷的地方，我需要计算总的积水量。
 * 好像可以这样想，对于每一个柱子，它上面能积的水的高度取决于它左右两边最高的柱子中较矮的那个，再减去它自己的高度。如果这个值是正的，就说明能积这么多水，否则就是积不了水。
 * 比如，看看第3个柱子，高度是0，它左边的柱子最高是1，右边的柱子最高是1，所以它能积的水是min(1,1) - 0 = 1。
 * 再看看第2个柱子，高度是1，它左边最高是1，右边最高是3，所以积水量是min(1,3) - 1 = 0，积不了水。
 * 这样看来，我需要为每一个柱子找到它左右两边最高的柱子，然后取较小的那个减去它自己的高度，就是它能积的水量。
 * （需要对着图形遍历一遍这个过程，用坐标点去判断，不要用区间的思路去判断，时刻关注每个数组元素左右的最大值 ）
 *
 * 优化思路：使用双指针的思路， 以每一个柱子作为参照系，对比其左右两边的柱子高度，判断是否可以积水。
 * 1：初始化两个指针：左指针 l 从数组开头开始，右指针 r 从数组末尾开始。
 * 2：维护两个变量：left_max 和 right_max，分别记录从左到 l 和从右到 r 的最高柱子高度。
 *
 * 3：移动指针并计算积水量：
 *    如果 height[l] < height[r]，则水的高度由左指针决定，若 height[l] < left_max，则计算积水量并累加；否则更新 left_max，然后左指针右移。
 *    否则，水的高度由右指针决定，若 height[r] < right_max，则计算积水量并累加；否则更新 right_max，然后右指针左移。
 *
 * 循环直到指针相遇：当 l >= r 时，结束循环并返回总的积水量。
 */
public class L_42 {
    public int trap(int[] height) {
        if(height == null || height.length == 0){
            return 0;
        }
        // 1:初始化两个指针
        int l = 0,r = height.length - 1;
        // 2: 维护两个变量：left_max 和 right_max，分别记录从左到 l 和从右到 r 的最高柱子高度。
        int left_max = 0,right_max = 0;
        int res = 0; // 统计结果

        while (l < r){
            // 水的高度有左指针决定
            if(height[l] < height[r]){
                // 如果左指针的柱子高度小于left_max，则计算积水量并累加
                if(height [l] < left_max){
                    res += left_max - height[l];
                }else {
                    left_max = height[l]; // 更新left_max
                }
                l++; // 左指针右移
            }else { // 水的高度由右指针决定
                if(height[r] < right_max){
                    res += right_max - height[r];
                }else {
                    right_max = height[r];// 更新right_max
                }
                r--; // 右指针左移
            }
        }
        return res;
    }

    /**
     * 总体思路：
     *
     * 首先，我得理解一下这个题目的意思。假设我有一个数组，比如[0,1,0,2,1,0,1,3,2,1,2,1]，这表示有12个柱子，高度分别是0,1,0,2,1,0,1,3,2,1,2,1。下雨后，雨水会积在凹陷的地方，我需要计算总的积水量。
     * 我想，可能需要找出每个柱子上面能积多少水，然后加起来就是总的积水量。那具体怎么算每个柱子上面能积多少水呢？
     * 好像可以这样想，对于每一个柱子，它上面能积的水的高度取决于它左右两边最高的柱子中较矮的那个，再减去它自己的高度。如果这个值是正的，就说明能积这么多水，否则就是积不了水。
     * 比如，看看第3个柱子，高度是0，它左边的柱子最高是1，右边的柱子最高是1，所以它能积的水是min(1,1) - 0 = 1。
     * 再看看第2个柱子，高度是1，它左边最高是1，右边最高是3，所以积水量是min(1,3) - 1 = 0，积不了水。
     * 这样看来，我需要为每一个柱子找到它左右两边最高的柱子，然后取较小的那个减去它自己的高度，就是它能积的水量。
     * 但是，这样做时间复杂度会不会太高？因为如果数组长度是n，那对于每个柱子，我都得扫描一遍左边和右边，时间复杂度是O(n^2)，这在n很大的时候会很慢。
     *
     * 有没有更好的办法呢？我记得有一种方法是用双指针，来优化这个过程。
     * 让我再想想，双指针是怎么用的呢？
     * 好像可以用两个指针，一个从左往右走，一个从右往左走，同时维护两个变量，记录左边最高的柱子和右边最高的柱子。
     * 具体来说，左指针开始在最左边，右指针开始在最右边。
     * 我还需要一个变量来记录总的积水量。
     * 然后，我比较左右指针所指的柱子的高度，如果左指针的高度小于右指针的高度，那么左指针所在的位置能积的水就是左最高柱子的高度减去它自己的高度，如果这个值大于0，就加到总的积水中，然后左指针右移。
     * 否则，如果右指针的高度小于等于左指针的高度，那么右指针所在的位置能积的水就是右最高柱子的高度减去它自己的高度，如果这个值大于0，就加到总的积水中，然后右指针左移。
     * 同时，我需要更新左最高柱子和右最高柱子的高度。
     */
}
